import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-08-17
 * Time: 23:12
 */
//https://leetcode.cn/problems/substring-with-concatenation-of-all-words/submissions/653975504/
public class Test {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList();
        int size = words.length;
        int len = words[0].length();
        int n = s.length() - size * len;
        if (n < 0) {
            return list;
        }
        HashMap<String, Integer> map = new HashMap();
        for (int i = 0; i < size; i++) {
            if (map.containsKey(words[i])) {
                map.put(words[i], map.get(words[i]) + 1);
            } else {
                map.put(words[i], 1);
            }
        }
        for (int i = 0; i <= n; i++) {
            HashMap<String, Integer> map2 = new HashMap(map);
            int j = i;
            String str = s.substring(j, j + len);
            while (map2.containsKey(str)) {
                int val = map2.get(str);
                if (val == 1) {
                    map2.remove(str);
                } else {
                    map2.put(str, val - 1);
                }
                if (map2.size() == 0) {
                    list.add(i);
                    break;
                }
                j += len;
                str = s.substring(j, j + len);
            }
        }
        return list;
    }

    public static void main(String[] args){
        String s="barfoothefoobarman";
        String[] arr={"foo","bar"};
        System.out.println(findSubstring(s,arr));
    }
}
